import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Solution1206 {

    public static class Node{
        int val;
        Node next;
        Node down;

        public Node(int val, Node next, Node down) {
            this.val = val;
            this.next = next;
            this.down = down;
        }
    }

    List<Node> list=new ArrayList<>();

    public Solution1206() {
    }

    public boolean search(int target) {
        if (list.size()==0){
            return false;
        }
        Node node=list.get(0);
        while (true){
            if (node.next.val>=target){
                if (node.down==null){
                    return node.next.val==target;
                }else{
                    node=node.down;
                }
            }else {
                node=node.next;
            }
        }
    }

    public void add(int num) {
        if (list.size()==0){
            list.add(new Node(Integer.MIN_VALUE,new Node(Integer.MAX_VALUE,null,null),null));
        }
        Node node=list.get(0);
        Stack<Node> stack=new Stack<>();
        while (true){
            if (node.next.val>=num){
                if (node.down==null){
                    node.next=new Node(num,node.next,null);
                    Node last=node.next;
                    while (!stack.isEmpty()){
                        if (Math.random()>0.5){
                            Node t=stack.pop();
                            t.next=new Node(num,t.next,last);
                            last=t.next;
                            if (stack.isEmpty()){
                                if (Math.random()>0.5){
                                    list.add(new Node(Integer.MIN_VALUE,new Node(num,new Node(Integer.MAX_VALUE,null,null),last),list.get(0)));
                                }
                            }
                        }else {
                            break;
                        }
                    }
                    return;
                }else {
                    stack.add(node);
                    node=node.down;
                }
            }else {
                node=node.next;
            }
        }
    }

    public boolean erase(int num) {
        if (list.size()==0){
            return false;
        }
        Node node=list.get(0);
        Stack<Node> stack=new Stack<>();
        while (true){
            if (node.next.val>=num){
                if (node.down==null){
                    if (node.next.val!=num){
                        return false;
                    }
                    Node last=node.next;
                    node.next=node.next.next;
                    while (!stack.isEmpty()){
                        Node t=stack.pop();
                        if (t.next.down!=last){
                            break;
                        }
                        last=t.next;
                        t.next=t.next.next;
                        if (stack.isEmpty()){
                            if (t.val==Integer.MIN_VALUE && t.next.val==Integer.MAX_VALUE){
                                list.remove(0);
                            }
                        }
                    }
                    return true;
                }else {
                    stack.add(node);
                    node=node.down;
                }
            }else {
                node=node.next;
            }
        }
    }

    public static void main(String[] args) {
        Solution1206 solution1206=new Solution1206();
        solution1206.add(1);
        solution1206.add(2);
        solution1206.add(3);
        System.out.println(solution1206.search(0));
        solution1206.add(4);
        System.out.println(solution1206.search(1));
        System.out.println(solution1206.erase(0));
        System.out.println(solution1206.erase(1));
        System.out.println(solution1206.search(1));
    }
}
